package com.sword.algorithm.matrix.breadthFirstSearch;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 宽度优先算法
 * BFS
 * Created by SwordLiu on 2018-02-03.
 */
public class BFS {

    public static void main(String[] args) {
        int[][] arr = {
                {1, 1, 0, 0, 0},
                {1, 0, 0, 0, 0},
                {0, 0, 0, 1, 0},
                {0, 0, 1, 1, 1},
                {0, 0, 1, 1, 1},
                {0, 0, 1, 1, 1}
        };
        new BFS().solution(arr);
    }

        public int[][] solution(int[][] matrix) {
            int w = matrix.length;
            int h = matrix[0].length;

            Queue<int[]> queue = new LinkedList<int[]>();
            for(int i = 0; i < w; i++) {
                for(int j = 0; j < h; j++) {
                    if (matrix[i][j] == 0) {
                        queue.offer(new int[]{i, j});
                    } else {
                        matrix[i][j] = -1;
                    }
                }
            }

            int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                for (int[] d : dirs) {
                    int r = cell[0] + d[0];
                    int c = cell[1] + d[1];
                    if (r < 0 || c < 0 || r >= w || c >= h || matrix[r][c] >= 0) {
                        continue;
                    }
                    matrix[r][c] = matrix[cell[0]][cell[1]] + 1;
                    queue.offer(new int[]{r, c});
                }
            }
            return matrix;
        }


}
